package com.example.searching_and_sorting;



import java.util.Iterator;

public class Sorting {
    /**
     * Sorts the specified array of integers using the selection
     * sort algorithm.
     *
     * @param data the array to be sorted
     */
    public static <T extends Comparable<T>> String selectionSort(int[] data)
    {
//        long startTime=System.nanoTime();   //获取开始时间
//        int Total_number_of_comparisons = 0;
        int min;
        T temp;
        for (int index = 0; index < data.length-1; index++)
        {
            min = index;

            for (int scan = index+1; scan < data.length; scan++) {
//                Total_number_of_comparisons++;
                if (data[scan]<data[min]) {
                    min = scan;

                }
            }
            swap(data, min, index);
        }
        String result = "选择排序：";
        for (int num : data)
        {
            result += num + " ";
        }
//        long endTime=System.nanoTime(); //获取结束时间
//        System.out.println("程序运行时间： "+(endTime-startTime)+"ns");
//        System.out.println("总比较次数： " + Total_number_of_comparisons);
        return result;
    }
    /**
     * 希尔排序
     * @param arrays 需要排序的序列
     */
    public static String Shell_Sort(int[] arrays){
        if(arrays == null || arrays.length <= 1){
            return null;
        }
        String result = "希尔排序：";
        //增量
        int incrementNum = arrays.length/2;
        while(incrementNum >=1){
            for(int i=0;i<arrays.length;i++){
                //进行插入排序
                for(int j=i;j<arrays.length-incrementNum;j=j+incrementNum){
                    if(arrays[j]>arrays[j+incrementNum]){
                        int temple = arrays[j];
                        arrays[j] = arrays[j+incrementNum];
                        arrays[j+incrementNum] = temple;
                    }
                }
            }
            //设置新的增量
            incrementNum = incrementNum/2;
        }
        for(int c : arrays){
            result+=c + " ";
        }
        result += "\n";
        return result;
    }
    /**
     * 堆排序
     */
    public static String HeapSort(int[] data) {
        ArrayHeap arrayHeap = new ArrayHeap();
        String result = "堆排序：";
        for (int i = 0;i<data.length;i++){
            arrayHeap.addElement(data[i]);
        }
        while (!(arrayHeap.isEmpty())){
            result += arrayHeap.removeMax() + " ";
        }
        result += "\n";
        return result;
    }
    /**
     * 二叉树排序
     */
    public static String Binarytree_sort(int[] data){
        LinkedBinarySearchTree linkedBinarySearchTree = new LinkedBinarySearchTree();
        String result = "二叉树排序：";
        for (int i = 0;i<data.length;i++){
            linkedBinarySearchTree.addElement(data[i]);
        }
        Iterator iterator = linkedBinarySearchTree.iteratorInOrder();
        while (iterator.hasNext()){
           result+=iterator.next() + " ";
        }
        result += "\n";
        return result;
    }
//    /**
//     * 间隔排序
//     */
//    public static String Gap_Sort(int[] elements , int gap){
//        String result = "";
//        int temp = 0;
//        while(gap >0)
//        {
//            for (int i = elements.length - 1; i >= 0; i--) {
//                for (int j = 0; j <= i - gap; j++) {
//                    if (elements[j] > elements[j + gap]) {
//                        temp = elements[j];
//                        elements[j] = elements[j + gap];
//                        elements[j + gap] = temp;
//                        for (int element : elements) {
//                            result += element + "\t";
//                        }
//                        result += "\n";
//                    }
//                }
//
//            }
//            gap= gap/2;
//        }
//        return result;
//    }

    /**
     * Swaps to elements in an array. Used by various sorting algorithms.
     *  @param data   the array in which the elements are swapped
     * @param index1 the index of the first element to be swapped
     * @param index2 the index of the second element to be swapped
     */
    private static <T extends Comparable<T>>
    void swap(int[] data, int index1, int index2)
    {
        int temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }

    /**
     * Sorts the specified array of objects using an insertion
     * sort algorithm.
     *
     * @param data the array to be sorted
     */
    public static <T extends Comparable<T>>
    String insertionSort(int[] data)
    {
        String result = "插入排序：";
        for (int index = 1; index < data.length; index++)
        {
            int key = data[index];
            int position = index;

            // shift larger values to the right
            while (position > 0 && data[position-1]>key)
            {
                data[position] = data[position-1];
                position--;
            }

            data[position] = key;
        }
        for (int d : data){
            result += d + " ";
        }
        return result + "\n";
    }

    /**
     * Sorts the specified array of objects using a bubble sort
     * algorithm.
     *
     * @param data the array to be sorted
     */
    public static <T extends Comparable<T>>
    String bubbleSort(int[] data)
    {
        int position, scan;
        int temp;

        for (position =  data.length - 1; position >= 0; position--)
        {
            for (scan = 0; scan <= position - 1; scan++)
            {
                if (data[scan]>data[scan+1]) {
                    swap(data, scan, scan + 1);
                }
            }
        }
        String result = "冒泡排序：";
        for (int d : data){
            result += d + " ";
        }
        return result + "\n";
    }

    /**
     * Sorts the specified array of objects using the merge sort
     * algorithm.
     *
     * @param data the array to be sorted
     */
    public static <T extends Comparable<T>>
    String mergeSort(int[] data)
    {
        mergeSort(data, 0, data.length - 1);
         String result = "归并排序：";
        for (int d : data){
            result += d + " ";
        }
        return result + "\n";
    }

    /**
     * Recursively sorts a range of objects in the specified array using the
     * merge sort algorithm.
     *  @param data the array to be sorted
     * @param min  the index of the first element
     * @param max  the index of the last element
     */
    private static <T extends Comparable<T>>
    void mergeSort(int[] data, int min, int max)
    {
        if (min < max)
        {
            int mid = (min + max) / 2;
            mergeSort(data, min, mid);
            mergeSort(data, mid+1, max);
            merge(data, min, mid, max);
        }
    }

    /**
     * Merges two sorted subarrays of the specified array.
     *  @param data the array to be sorted
     * @param first the beginning index of the first subarray
     * @param mid the ending index fo the first subarray
     * @param last the ending index of the second subarray
     */
    @SuppressWarnings("unchecked")
    private static <T extends Comparable<T>>
    void merge(int[] data, int first, int mid, int last)
    {
        int[] temp = new int[data.length];

        int first1 = first, last1 = mid;  // endpoints of first subarray
        int first2 = mid+1, last2 = last;  // endpoints of second subarray
        int index = first1;  // next index open in temp array

        //  Copy smaller item from each subarray into temp until one
        //  of the subarrays is exhausted
        while (first1 <= last1 && first2 <= last2)
        {
            if (data[first1]<data[first2])
            {
                temp[index] = data[first1];
                first1++;
            }
            else
            {
                temp[index] = data[first2];
                first2++;
            }
            index++;
        }
        //  Copy remaining elements from first subarray, if any
        while (first1 <= last1)
        {
            temp[index] = data[first1];
            first1++;
            index++;
        }
        //  Copy remaining elements from second subarray, if any
        while (first2 <= last2)
        {
            temp[index] = data[first2];
            first2++;
            index++;
        }
        //  Copy merged data into original array
        for (index = first; index <= last; index++)
            data[index] = temp[index];
    }

    /**
     * Sorts the specified array of objects using the quick sort algorithm.
     *
     * @param data the array to be sorted
     */
    public static <T extends Comparable<T>>
    String quickSort(int[] data)
    {
        quickSort(data, 0, data.length - 1);
        String result = "快速排序：";
        for (int d : data){
            result += d + " ";
        }
        return result + "\n";
    }

    /**
     * Recursively sorts a range of objects in the specified array using the
     * quick sort algorithm.
     *  @param data the array to be sorted
     * @param min  the minimum index in the range to be sorted
     * @param max  the maximum index in the range to be sorted
     */
    private static <T extends Comparable<T>>
    void quickSort(int[] data, int min, int max)
    {
        if (min < max)
        {
            // create partitions
            int indexofpartition = partition(data, min, max);

            // sort the left partition (lower values)
            quickSort(data, min, indexofpartition - 1);

            // sort the right partition (higher values)
            quickSort(data, indexofpartition + 1, max);
        }
    }

    /**
     * Used by the quick sort algorithm to find the partition.
     *  @param data the array to be sorted
     * @param min  the minimum index in the range to be sorted
     * @param max  the maximum index in the range to be sorted
     */
    private static <T extends Comparable<T>>
    int partition(int[] data, int min, int max)
    {
        int partitionelement;
        int left, right;
        int middle = (min + max) / 2;

        // use the middle data value as the partition element
        partitionelement = data[middle];
        // move it out of the way for now
        swap(data, middle, min);

        left = min;
        right = max;

        while (left < right)
        {
            // search for an element that is > the partition element
            while (left < right && data[left]<=partitionelement)
                left++;

            // search for an element that is < the partition element
            while (data[right]>partitionelement)
                right--;

            // swap the elements
            if (left < right)
                swap(data, left, right);
        }

        // move the partition element into place
        swap(data, min, right);

        return right;
    }

    public static <T extends Comparable<T>> String gapSort (int[] data, int i)
    {
        int position, scan;
        int temp;

        while(i > 0)
        {
            for (position = data.length - 1; position >= 0; position--)
            {
                for (scan = 0; scan <= position - 1; scan++)
                {
                    if (i > scan)
                    {
                        if (data[scan]>data[scan+i])
                        {
                            /** Swap the values */
                            temp = data[scan];
                            data[scan] = data[scan + i];
                            data[scan + i] = temp;
                        }
                    }
                    else
                    {
                        if (data[scan]<data[scan-i])
                        {
                            temp = data[scan];
                            data[scan] = data[scan - i];
                            data[scan - i] = temp;
                        }
                    }

                }
            }
            i--;
        }
        String result = "间隔排序：";
        for (int d : data){
            result += d + " ";
        }
        return result + "\n";
    }
}
